package data_structure.mooc;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
public class BucketSort {

    private BucketSort() {

    }

    public static void sort(Integer[]arr,int bucket){

        Integer []temp=new Integer[arr.length];
        sort (arr,0,arr.length-1,bucket,temp);
    }
    /**
     * 使用辅助空间，对位于[left,right]中的数字排序
     * [left,right]===>分成bucket个桶
     * d=(right-left+1)/bucket（上取整）
     * bucket[0]==[a,a+d]
     * bucket[1]==[a+d+1,a+2d+1]
     * .....
     * 分别对每个桶进行计数排序,递归调用
     * @param arr
     * @param left
     * @param right
     * @param bucket
     * @param temp
     */
    public static void sort(Integer []arr,int left,int right,int bucket,Integer[]temp){
        if(left>=right)return;
        //求最大子和最小值
        int max=Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for (int i = left; i <=right; i++) {
            max=Math.max (max, arr[i]);
            min=Math.min (min, arr[i]);
        }

        if(max==min)return;
        int d=(max-min+1)/bucket+((max - min+1)%bucket==0?0:1);
        int []cnt=new int[bucket];
        int []index=new int[bucket+1];

        for(int i=left;i<=right;i++){
            cnt[(arr[i]-min)/d]++;
        }

        for(int i=0;i+1<index.length; i++){
            index[i+1] =index[i]+cnt[i];
        }

        for(int i=left;i<=right;i++){
            temp[left+index[(arr[i]-min)/d]]=arr[i];
            index[(arr[i]-min)/d]++;
        }
        for(int i=left;i<=right; i++){
            arr[i]=temp[i];
        }
        //递归进行排序，先对第一个桶
        sort(arr,left,left+index[0]-1,bucket,temp);
        for(int i=0;i+1<index.length-1;i++){
            sort(arr,left+index[i],left+index[i+1]-1,bucket,temp);
        }
    }

    /**
     * 用数组来储存每一个桶，桶中元素采用链表的方式存储数组
     * count
     * 计算有多少个桶
     * 根据一定规则将数组中元素定位到每一个桶中
     * 对每一个桶进行排序
     * 整合结束
     * @param arr
     * @param count 每一个桶中含元素的个数
     */
    public static void sort2(Integer []arr,int count){

        if(arr.length<=1){
            return;
        }
        int max=Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for (int i = 0; i <arr.length; i++) {
            max=Math.max (max, arr[i]);
            min=Math.min (min, arr[i]);
        }
        if(max==min)return;
        //桶的个数
        int bucket=arr.length/count+(arr.length%count==0?0:1);
        LinkedList<Integer>[]buckets=new LinkedList[bucket];
        //初始化桶
        for(int i=0;i<bucket;i++){
            buckets[i]=new LinkedList<Integer> ();
        }
        //将arr[i]定位到桶中
        int range=(max-min+1)/bucket+((max-min+1)%bucket==0?0:1);
        for(int el:arr){
            buckets[(el-min)/range].add (el);
        }
        //对每一个桶进排序,默认为冒泡排序
        for(int i=0;i<bucket;i++){
            Collections.sort (buckets[i]);
        }
        int index=0;
        for(int i=0;i < bucket; i++){
            for(int j=0;j<buckets[i].size(); j++){
                arr[index++]=buckets[i].get(j);
            }
        }
    }
}
